package com.jiang.daily.Q2070;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/09 0:50
 */
class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        int n = queries.length;
        int[] arr = new int[n];

        Arrays.sort(items, (v1, v2) -> Integer.compare(v1[0], v2[0]));

        int len = items.length;
        for (int i = 1; i < len; i++) {
            items[i][1] = Math.max(items[i][1], items[i - 1][1]);
        }

        for (int i = 0; i < n; i++) {
            int l = 0, r = len - 1;
            while (l <= r) {
                int mid = (r - l) / 2 + l;
                if (items[mid][0] > queries[i]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (l == 0) {
                arr[i] = 0;
            } else {
                arr[i] = items[l - 1][1];
            }
        }
        return arr;
    }
}
